package SwordForOffer.Problem37;

import java.util.Stack;

public class FindFirstCommonCode {
	/*
	 * 求两个单向链表的第一个公共节点
	 */
	public ListNode findFirstCommonNode(ListNode root1,ListNode root2)
	{
		int length1=getLength(root1);
		int length2=getLength(root2);

		ListNode pointLongListNode=null;
		ListNode pointShortListNode=null;

		int dif=0;
		if(length1>length2)
		{
			pointLongListNode=root1;
			pointShortListNode=root2;
			dif=length1-length2;
		}
		else {
			pointLongListNode=root2;
			pointShortListNode=root1;
			dif=length2-length1;
		}

		for(int i=0;i<dif;i++)
			pointLongListNode=pointLongListNode.nextNode;

		while(pointLongListNode!=null && pointShortListNode!=null && pointLongListNode!=pointShortListNode)
		{
			pointLongListNode=pointLongListNode.nextNode;
			pointShortListNode=pointShortListNode.nextNode;
		}
		return pointLongListNode;		
	}
	private int getLength(ListNode root)
	{
		int result=0;
		if(root==null)
			return result;
		ListNode point=root;
		while(point!=null)
		{
			point=point.nextNode;
			result++;
		}
		return result;
	}

	public ListNode myFindFirstCommonNode(ListNode head1, ListNode head2) {
		if (head1 == null || head2 == null){
			return null;
		}
		Stack<ListNode> stack1 = new Stack<>();
		Stack<ListNode> stack2 = new Stack<>();
		stack1.push(head1);
		stack2.push(head2);
		ListNode current1  = head1;
		ListNode current2 = head2;
		while (current1.nextNode != null){
			current1 = current1.nextNode;
			stack1.push(current1);
		}
		while (current2.nextNode != null){
			current2 = current2.nextNode;
			stack2.push(current2);
		}
		if (stack1.peek() != stack2.peek()){
			return null;
		}
		while (stack1.peek() != null && stack2.peek() != null){
			current1 = stack1.pop();
			if (current1 != stack2.pop()){
				return current1.nextNode;
			}
		}
		if (stack1.peek() != null){
			return stack1.peek().nextNode;

		}else{
			return stack2.peek().nextNode;
		}
	}
}
class ListNode {
	int data;
	ListNode nextNode;
}
